package com.jiang.专题.数组.Q122;

/**
 * @author Jiang
 * @version 1.0
 * @date 2024/12/15 18:42
 */
class Solution {
    // 贪心
    // public int maxProfit(int[] prices) {
    //     int ans = 0;
    //     int n = prices.length;
    //     for (int i = 1; i < n; ++i) {
    //         ans += Math.max(0, prices[i] - prices[i - 1]);
    //     }
    //     return ans;
    // }

    // 动态规划
    public int maxProfit(int[] prices) {
        int len = prices.length;
        // 表示从当前开始直到数组最后的的最大盈利
        int[] temp = new int[len];
        temp[len - 1] = 0;
        int maxProfit = 0;  // 最大盈利
        int differ = 0; // 当天与后面任意一天盈利最大值
        // 从后往前遍历每一天
        for (int i = len - 2; i >= 0; i--) {
            differ = 0;
            // 从天数 i 开始往后遍历，求得天数 i 盈利temp[i]最大值
            for (int j = i + 1; j < len; j++) {
                differ = Math.max(differ, prices[j] - prices[i]);
                // 天数 i 与天数 j 的盈利 + 天数 j 的最大盈利 是否大于最大盈利
                if (differ + temp[j] > maxProfit) {
                    maxProfit = differ + temp[j];
                }
            }
            temp[i] = maxProfit;
        }
        return maxProfit;
    }
}
